package 构建前缀信息的技巧_解决子数组相关问题;

// 利用前缀和快速得到区域累加和
// 测试链接 : https://leetcode.cn/problems/range-sum-query-immutable/
public class Code01_PrefixSumArray {

    class NumArray{

        // 从1开始(不用考虑left=0时)，记录nums数组的前i个累加和
        // nums:  3, 2, -5, 6, 2, 1
        // sum：   0, 3, 5, 0, 6, 8, 9
        public int[] sum;
        public NumArray(int[] nums) {
            sum = new int[nums.length+1];
            for(int i = 1; i <= nums.length; i++){
                sum[i] = sum[i-1] + nums[i-1];
            }
        }

        // left~right：[0~right] - [0~left-1]
        // sum[right+1]-sum[left]
        public int sumRange(int left, int right) {
            return sum[right+1] - sum[left];
        }
    }
}
